package com.yiwenup.struct._05_unionfind;

import com.yiwenup.struct._05_unionfind.base.UnionFind;

/**
 * 并查集：快速查找实现
 * <p>
 * 时间复杂度：find - O(logn)；union - O(logn)
 **/
public class QuickUnionV1 extends UnionFind {
    public QuickUnionV1(int capacity) {
        super(capacity);
    }

    @Override
    public int find(int v) {
        rangeCheck(v);
        while (v != parents[v]) {
            v = parents[v];
        }
        return v;
    }

    /**
     * 将 {@param v1} 所在集合的根节点设置为  {@param v2} 的根节点
     */
    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;
        parents[p1] = p2;
    }
}
